# -*- coding: utf-8 -*-
# 给定两个二进制字符串，返回他们的和（用二进制表示）

# 输入为非空字符串且只包含数字 1 和 0
# 示例 1:
# 输入: a = "11", b = "1"
# 输出: "100"

# 示例 2:
# 输入: a = "1010", b = "1011"
# 输出: "10101"

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if len(a) == 0 or len(b) == 0:
            return a + b;

        if len(a) > len(b):
            b = "0" * (len(a) - len(b)) + b;
        else:
            a = "0" * (len(b) - len(a)) + a;

        overflow = 0;
        rtn = "";
        for i in range(len(a) - 1, -1, -1):
            sum = ord(a[i]) - ord("0") + ord(b[i]) - ord("0") + overflow;
            rtn = str(sum % 2) + rtn;
            overflow = sum // 2;

        if overflow != 0:
            rtn = str(overflow) + rtn;

        return rtn;

t = Solution();
print t.addBinary("1010", "1011");